package com.leetcode.p200;

import com.bean.TreeNode;
import com.utils.TreeUtils;

public class Test235 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

//        if (p.val == root.val) {
//            return root;
//        } else if (q.val == root.val) {
//            return root;
//        } else if (p.val < root.val && q.val > root.val || q.val < root.val && p.val > root.val) {
//            return root;
//        } else if (q.val > root.val) {
//            return lowestCommonAncestor(root.right, p, q);
//        } else {
//            return lowestCommonAncestor(root.left, p, q);
//        }

        if (p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        } else if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        } else {
            return root;
        }
    }

    public static void main(String[] args) {
//        TreeNode treeNode = TreeUtils.buildTree("6,2,8,0,4,7,9,null,null,3,5");
        TreeNode treeNode = TreeUtils.buildTree("2,1,3");
        TreeUtils.showTree(treeNode);

        Test235 test = new Test235();
//        TreeNode result = test.lowestCommonAncestor(treeNode, new TreeNode(2), new TreeNode(8));
//        TreeNode result = test.lowestCommonAncestor(treeNode, new TreeNode(2), new TreeNode(4));
        TreeNode result = test.lowestCommonAncestor(treeNode, new TreeNode(3), new TreeNode(1));
        System.out.println(result.val);
    }

}
